/*
https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode-solution/
 */
import java.util.*;

public class Solution336 {

    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String,Integer> map=new HashMap<>();
        for (int i=0;i< words.length;i++){
            map.put(words[i],i);
        }
        List<List<Integer>> ans=new ArrayList<>();
        for (int i=0;i<words.length;i++){
            String word=words[i];
            for (int j=word.length();j>=0;j--){
                if (check(word.substring(j))){
                    int t=map.getOrDefault(new StringBuilder(word.substring(0,j)).reverse().toString(),-1);
                    if (t!=-1 && t!=i){
                        ans.add(Arrays.asList(i,t));
                    }
                }
            }
            for (int j=1;j<=word.length();j++){
                if (check(word.substring(0,j))){
                    int t=map.getOrDefault(new StringBuilder(word.substring(j)).reverse().toString(),-1);
                    if (t!=i && t!=-1){
                        ans.add(Arrays.asList(t,i));
                    }
                }
            }
        }
        return ans;
    }

    boolean check(String s){
        int l=0,r=s.length()-1;
        while (l<r){
            if (s.charAt(l)!=s.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution336().palindromePairs(new String[]{"abcd","dcba","lls","s","sssll"}));
    }
}
